// https://www.lintcode.com/problem/perfect-squares/description
// 动态规划O(N根号N)，放缩夹逼，见evernote
class Solution {
public:
    /**
     * @param n: a positive integer
     * @return: An integer
     */
    int numSquares(int n) {
        vector<int> res(n + 1, INT_MAX);
        res[0] = 0;
        for (int i = 1; i < n + 1; ++i)
        {
            // for (int j = sqrt(i); j >= 0; --j) 正过来倒过来都行，反正i是正序的
            for (int j = 1; j <= sqrt(i); ++j)
            {
                if (res[i - j * j] != INT_MAX)
                    res[i] = min(res[i], res[i - j * j] + 1);
            }
        }
        return res.back();
    }
};

class Solution {
public:
    int numSquares(int n) {
        vector<int> rec(n + 1, n + 1);
        rec[0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= sqrt(i); ++j) {
                rec[i] = min(rec[i], rec[i - j * j] + 1);
            }
        }
        return rec.back();
    }
};